#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
namespace work1
{
    const int N=10;
    pair<int,int> a[N];
    vector<pair<int,int> > e;
    int ans1=-1e18,ans2=0;
    int f[N][N],floyd[N][N];
    const int inf=1e18;
    void dfs(int x,int cnt)
    {
        if(cnt<0) return ;
        if(x==e.size())
        {
            if(cnt!=0) return ;
            memcpy(floyd,f,sizeof(f));
            for(int k=1;k<=n;k++)
                for(int i=1;i<=n;i++)
                    for(int j=1;j<=n;j++)
                        floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]);
            // for(int i=1;i<=n;i++)
            // {
            //     for(int j=1;j<=n;j++)
            //         cout<<f[i][j]<<" ";
            //     cout<<'\n';
            // }
            // for(int i=1;i<=n;i++)
            // {
            //     for(int j=1;j<=n;j++)
            //         cout<<floyd[i][j]<<" ";
            //     cout<<'\n';
            // }
            int sum=0;
            for(int i=1;i<=m;i++) sum=max(-inf,sum-floyd[a[i].first][a[i].second]);
            if(sum>ans1) ans1=sum,ans2=0;
            if(sum==ans1) ans2++;
            return ;
        }
        f[e[x].first][e[x].second]=f[e[x].second][e[x].first]=1;
        dfs(x+1,cnt-1);
        f[e[x].first][e[x].second]=f[e[x].second][e[x].first]=inf;
        dfs(x+1,cnt);
    }
    void main()
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++) 
        {
            int x,y;
            cin>>x>>y;
            a[i]=make_pair(x,y);
        }
        memset(f,0x3f,sizeof(f));
        for(int i=1;i<=n;i++) f[i][i]=0;
        e.clear(),ans1=-1e18,ans2=0;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                e.push_back(make_pair(i,j));
        dfs(0,m-1);
        cout<<ans1<<' '<<ans2<<'\n';
    }
}
namespace work2
{
    void main()
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++) 
        {
            int x,y;
            cin>>x>>y;
        }
        cout<<-2*(n-1)<<' '<<1<<'\n';
    }
}
namespace work3
{
    const int N=2010;
    vector<int> a[N];
    pair<int,int> ban[N*N];
    int d[N];
    int bfs(int x,int y)
    {
        for(int i=1;i<=n;i++) d[i]=-1;
        queue<int> q;
        q.push(x),d[x]=0;
        while(q.size())
        {
            x=q.front();
            q.pop();
            if(x==y) return d[x];
            for(int to:a[x])
            {
                if(d[to]!=-1) continue;
                d[to]=d[x]+1;
                q.push(to);
            }
        }
        return 1e18;
    }
    void main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) a[i].clear();
        for(int i=1;i<=m;i++) 
        {
            int x,y;
            cin>>x>>y;
            a[x].push_back(y);
            a[y].push_back(x);
            ban[i]=make_pair(x,y);
        }
        int ans=1e18;
        for(int i=1;i<=m;i++)
        {
            int x=ban[i].first,y=ban[i].second;
            a[x].erase(find(a[x].begin(),a[x].end(),y));
            a[y].erase(find(a[y].begin(),a[y].end(),x));
            ans=min(ans,bfs(x,y));
            a[x].push_back(y),a[y].push_back(x);
        }
        cout<<-(m+ans-1)<<' '<<1<<'\n';
    }
}
signed main()
{
    freopen("oi.in","r",stdin);
    freopen("oi.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int c,t;
    cin>>c>>t;
    while(t--)
    {
        if(c<=2) work1::main();
        else if(c<=4) work2::main();
        else work3::main();
    }
    return 0;   
}